package graph.weighted.maxFlow;
/**
 * 
 * @Title: CandyMaxFlow.java 
 * @Package graph.weighted.maxFlow 
 * @Description: 解决最大流问题
 * @author CandyWall   
 * @date 2021年1月23日 上午8:30:51 
 * @version V1.0
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

import graph.weighted.CandyWeightedGraph;

public class CandyMaxFlow {
    private CandyWeightedGraph network;           // 原始图
    private int s, t; // 源点和汇点
    private int maxFlow;
    private CandyWeightedGraph residualGraph;   // 残量图
    
    public CandyMaxFlow(CandyWeightedGraph network, int s, int t) {
        if(!network.isDirected()) {
            throw new IllegalArgumentException("该类只能用于有向图求最大流问题！");
        }
        // 因为至少包含一个源点和汇点，所以顶点数最少为2
        if(network.getVertex_num() < 2) {
            throw new IllegalArgumentException("因为至少包含一个源点和汇点，所以顶点数最少为2！");
        }
        this.network = network;
        network.validateVertex(s);
        network.validateVertex(t);
        this.s = s;
        this.t = t;
        
        // 残量图初始化
        this.residualGraph = new CandyWeightedGraph(network.getVertex_num(), true);
        for(int v = 0; v < network.getVertex_num(); v++) {
            for(int w : network.adjacentVertexes(v)) {
                int capacity = network.getWeight(v, w); 
                residualGraph.addEdge(v, w, capacity);
                residualGraph.addEdge(w, v, 0);
            }
        }
        
        // 在残量图中不断寻找增广路径
        while(true) {
            // 获取增广路径
            ArrayList<Integer> augPath = getAugmentingPath();
            if(augPath.size() == 0) {
                break;
            }
            
            // 计算增广路径上的最小值
            int f = Integer.MAX_VALUE;
            for(int i = 1; i < augPath.size(); i++) {
                int v = augPath.get(i - 1);
                int w = augPath.get(i);
                f = Math.min(f, residualGraph.getWeight(v, w));
            }
            
            maxFlow += f;
            
            //根据增广路径更新残量图
            for(int i = 1; i < augPath.size(); i++) {
                int v = augPath.get(i - 1);
                int w = augPath.get(i);
                // 判断增广路径中的某条边vw是正向边还是反向边
                // 如果vw是正向边，在原图中肯定包含这条边，正向边的权值表示这条边还剩下多少容量
                // 由于流量增加了f，所以正向边容量相应减少f，反向边容量相应增加f
                /*if(network.hasEdge(v, w)) {
                    residualGraph.setWeight(v, w, residualGraph.getWeight(v, w) - f);
                    residualGraph.setWeight(w, v, residualGraph.getWeight(w, v) + f);
                }
                // 如果vw是反向边，wv就是正向边，流量从v流到w抵消了wv的正向边的流量，wv的容量相应增加，即wv的权值增加
                else {
                    residualGraph.setWeight(w, v, residualGraph.getWeight(w, v) + f);
                    residualGraph.setWeight(v, w, residualGraph.getWeight(v, w) - f);
                }*/
                // 由此可见，不管vw是正向边还是反向边，对残量图中某个边的权值的修改操作都是一样的，上述判断可以简化为：
                residualGraph.setWeight(w, v, residualGraph.getWeight(w, v) + f);
                residualGraph.setWeight(v, w, residualGraph.getWeight(v, w) - f);
            }
        }
    }

    // 遍历残量图获取增广路径
    private ArrayList<Integer> getAugmentingPath() {
        ArrayList<Integer> augmentingPath = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        
        int[] pres = new int[residualGraph.getVertex_num()];
        Arrays.fill(pres, -1);
        queue.add(s);
        pres[s] = s;
        
        while(!queue.isEmpty()) {
            int cur = queue.remove();
            if(cur == t) {
                break;
            }
            for(int next : residualGraph.adjacentVertexes(cur)) {
                if(pres[next] == -1 && residualGraph.getWeight(cur, next) > 0) {
                    pres[next] = cur;
                    queue.add(next);
                }
            }
        }
        
        if(pres[t] == -1) {
            return augmentingPath;
        }
        
        int cur = t;
        while(cur != s) {
            augmentingPath.add(cur);
            cur = pres[cur];
        }
        augmentingPath.add(s);
        Collections.reverse(augmentingPath);
        
        return augmentingPath;
    }

    /**
     * 获取这个网络的最大流
     * @return
     */
    public int getMaxFlow() {
        return maxFlow;
    }
    
    /**
     * 获取流经某条边的流量
     * @param v
     * @param w
     * @return
     */
    public int flow(int v, int w) {
        if(!network.hasEdge(v, w)) {
            throw new IllegalArgumentException("网络中边不存在！");
        }
        // 返回残量图中反向边的权值（vw的流量是多少，那么反向边wv就可以抵消多少流量）
        return residualGraph.getWeight(w, v);
    }

    public static void main(String[] args) {
        CandyWeightedGraph network1 = new CandyWeightedGraph("testData/weightedGraph/maxFlow/network1.txt", true);
        CandyMaxFlow flow1 = new CandyMaxFlow(network1, 0, 3);
        System.out.println("最大流：" + flow1.getMaxFlow());
        for(int v = 0; v < network1.getVertex_num(); v++) {
            for(int w : network1.adjacentVertexes(v)) {
                System.out.println(String.format("%d-%d : %d / %d", v, w, flow1.flow(v, w), network1.getWeight(v, w)));
            }
        }
        System.out.println("-----------------------------");
        CandyWeightedGraph network2 = new CandyWeightedGraph("testData/weightedGraph/maxFlow/network2.txt", true);
        CandyMaxFlow flow2 = new CandyMaxFlow(network2, 0, 5);
        System.out.println("最大流：" + flow2.getMaxFlow());
        for(int v = 0; v < network2.getVertex_num(); v++) {
            for(int w : network2.adjacentVertexes(v)) {
                System.out.println(String.format("%d-%d : %d / %d", v, w, flow2.flow(v, w), network2.getWeight(v, w)));
            }
        }
        System.out.println("-----------------------------");
        CandyWeightedGraph network3 = new CandyWeightedGraph("testData/weightedGraph/maxFlow/baseball.txt", true);
        CandyMaxFlow flow3 = new CandyMaxFlow(network3, 0, 10);
        System.out.println("最大流：" + flow3.getMaxFlow());
        for(int v = 0; v < network3.getVertex_num(); v++) {
            for(int w : network3.adjacentVertexes(v)) {
                System.out.println(String.format("%d-%d : %d / %d", v, w, flow3.flow(v, w), network3.getWeight(v, w)));
            }
        }
    }
}
